class DSU:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n

    def find(self, i: int) -> int:
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int) -> bool:
        i, j = self.find(i), self.find(j)
        if i != j:
            if i < j:
                self._array[j] = i
            else:
                self._array[i] = j
            return True
        else:
            return False

    def is_connected(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)

    @property
    def group_num(self):
        """计算连通分支数量"""
        return len(set(self._array))

    @property
    def max_group_size(self):
        """计算最大连通分支包含的数量"""
        import collections
        return max(collections.Counter(self._array).values())


class Solution:
    def smallestEquivalentString(self, a: str, b: str, s: str) -> str:
        size1, size2 = len(a), len(s)

        dsu = DSU(26)

        for i in range(size1):
            dsu.union(ord(a[i]) - 97, ord(b[i]) - 97)

        ans = []
        for i in range(size2):
            ans.append(chr(dsu.find(ord(s[i]) - 97) + 97))
        return "".join(ans)


if __name__ == "__main__":
    # "makkek"
    print(Solution().smallestEquivalentString(a="parker", b="morris", s="parser"))

    # "hdld"
    print(Solution().smallestEquivalentString(a="hello", b="world", s="hold"))

    # "aauaaaaada"
    print(Solution().smallestEquivalentString(a="leetcode", b="programs", s="sourcecode"))
